%Model matematyczny problemu

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Wejście}
Na wejściu przyjmowany jest zbiór stanów odpowiadający $k$ kolorom żetonów na planszy oraz polu pustemu, a także macierz wejściową $M$ reprezentującą planszę:
\begin{eqnarray*}
S = \{0, 1, \dots, k\} 	& \textrm{gdzie} & k \in \mathbb{N} \\
M \in M_{m\times n} 	& \textrm{gdzie} & m, n \in \mathbb{N}\\
M_{i,j}\in	S 			& \textrm{gdzie} & i \in [0, 1, \dots, m-1],  j \in [0, 1, \dots, n-1]
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Krok algorytmu}
Każdy krok $s_i$ jest złożony z dwóch przekształceń:

\begin{itemize}
\item wyszukania sąsiadów $f_i$
\item eliminacji grupy $e_i$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Operacja wyszukania sąsiadów}\label{seq:search}
Operacja wyszukania ma na celu zebranie współrzędnych wszystkich żetonów należących do tej samej grupy względem żetonu o zadanych współrzędnych. Formalnie operacja ta wyznacza zbiór $D$ wszystkich współrzędnych będących w sąsiedztwie współrzędnej $w_i$. Funkcja $f_i$ jest wywoływana rekurencyjnie $j$ razy dla kolejnych zbiorów $D_j$ do momentu, gdy rozmiar zbioru przestaje się powiększać:
\begin{eqnarray*}
f_i (M_{i-1}, D_{j-1}) = D_{j}
\end{eqnarray*}

Operacja ta aplikuje następujące przekształcenie:
\begin{itemize}
\item Krok 0:
\begin{equation*}
D_{0} = \{w_i = (x_i, y_i)\}
\end{equation*}

\item Krok 1:
\begin{eqnarray*}
\forall_{w = (x, y) \in D_{j-1}} \colon 
\end{eqnarray*}
\begin{equation*}
\left\{\begin{array}{llll}
\forall_{w' = (x', y)} & (|x - x'| = 1) \wedge (M_{w} = M_{w'}) & \Rightarrow & D_j = D_j \cup {w'} \\
\forall_{w' = (x, y')} & (|y - y'| = 1) \wedge (M_{w} = M_{w'}) & \Rightarrow & D_j = D_j \cup {w'}   
\end{array}\right.
\end{equation*}

\item Krok 2: 
\begin{equation*}
\begin{array}{llll}
\textrm{dopóki} &  D_j \neq D_{j-1} & \textrm{goto} & 1
\end{array}
\end{equation*}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Operacja eliminacji grupy}
Zadaniem operacji eliminacji grupy jest usunięcie żetonów zgodnie z zasadami obowiązującymi w grze SameGame. Operacja ta przekształca macierz wejściową na podstawie zbioru $D$ wyznaczonego przez operację wyszukania i zwraca macierz stanu planszy po $i$-tym przekształceniu:
\begin{eqnarray*}
e_i (M_{i-1}, D) = M_{i}
\end{eqnarray*}

Operacja ta aplikuje następujące przekształcenia:
\begin{eqnarray*}
\forall_{d_i = (x_i, y_i) \in D} \colon
\end{eqnarray*}
\begin{equation*}
\left\{\begin{array}{lll}
M^{i+1}_{x,y+1} = M^{i}_{x,y} & \textrm{dla} & x = x_i \land y < y_i\\
M^{i+1}_{x,y} = 0 & \textrm{dla} & x = x_i \land y = 0\\
M^{i+1}_{x,y} = M^{i}_{x,y} & \textrm{dla reszty} & x, y\\
\end{array}\right.
\end{equation*}

\begin{eqnarray*}
\forall_{c_{i} = (y_0, \dots, y_n) \in M} \colon \sum_{j=0}^n y_j = 0
\end{eqnarray*}
\begin{equation*}
\left\{\begin{array}{lll}
M^{i+1}_{x-1,y} = M^{i}_{x,y} & \textrm{dla} & x_i \geq x\\
M^{i+1}_{x,y} = M^{i}_{x,y} & \textrm{dla reszty} & x, y\\
\end{array}\right.
\end{equation*}

Gdzie:
\begin{eqnarray*}
M^{i}_{x,y} & - & \textrm{Macierz $M$ po przekształceniu $i$, element o współrzędnych } (x, y)\\
M^{i+1}_{x,y} & - & \textrm{Macierz $M$ po przekształceniu $i+1$, element o współrzędnych } (x, y)\\
c_i & - & i\textrm{-ta kolumna macierz $M$}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Macierz wynikowa}
Macierz wynikowa $E$ musi spełniać następujący warunek:
\begin{equation*}
\forall_{w_i = (x_i, y_i)} \colon E_{w_i} \neq 0 \Rightarrow f_{i} \colon (E, \{w_i\}) = \emptyset
\end{equation*}

Gdzie:
\begin{eqnarray*}
f_{i} & - & \textrm{operacja sąsiedztwa zdefiniowana przez operację wyszukania (patrz \ref{seq:search})}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Wyjście}
Na wyjściu zwracana jest sekwencja współrzędnych $W$, na których była podjęta akcja zdjęcia grupy żetonów w czasie każdego z $r$ ruchów:
\begin{eqnarray*}
W = (w_1, w_2, \dots, w_r)  & \textrm{gdzie} & r \in \mathbb{N} \\
w_i = (x_i, y_i) & \textrm{gdzie} & x \in [0, 1, \dots, m-1], y \in [0, 1, \dots, n-1]
\end{eqnarray*}

Oraz macierz wynikowa $E$, wygenerowana na podstawie macierzy wejściowej oraz sekwencji współrzędnych za pomocą funkcji $s_i$:
\begin{eqnarray*}
s_i (M_{i-1}, w_i) = M_{i}\\
s_r (M_{r-1}, w_r) = E
\end{eqnarray*}

Gdzie:
\begin{eqnarray*}
E & - & \textrm{macierz wynikowa} \\
M_i & - & \textrm{macierz stanu planszy po i-tym przekształceniu}\\
r & - & \textrm{liczba wszystkich przekształceń}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Kryterium optymalizacji}
Rozwiązanie problemu polega na minimalizowaniu mocy podzbioru $P$ niezerowych elementów w~macierzy wynikowej $E$ wybraną funkcją $g$ generującą rozwiązanie:
\begin{eqnarray*}
%\forall_{w_i = (x_i, y_i)} & w_i \in P \Leftrightarrow E_{w_i} \neq 0\\
s(M_0,(w_1,w_2,\dots,w_{n-1},w_n))=E\\
P(E) = \{(x,y)\in E, E_{(x,y)} \neq 0\}\\
g(M_0,(w_1,\dots,,w_n))&=&|P(s(M_0,(w_1,\dots,w_n)))| \rightarrow min
\end{eqnarray*}
Gdzie:
\begin{eqnarray*}
E & - & \textrm{macierz wynikowa} \\
P(E) & - & \textrm{zbiór niezerowych elementów macierzy E}\\
g & - & \textrm{wynik gry}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%